The present invention relates in general to disk operating systems and in particular to a method for mapping the virtual address space of a process into real core and disk storage space.
In multi-programming computer operating systems a number of independent processes share the use of the central processing hardware of a computer system according to a time sharing allocation method. While the program associated with the process may appear to a user to run continuously, the process normally has continuous use of the system processing hardware only for a short period, long enough to execute a portion of the program, and then relinquishes use of the processor to another process. Thus, when several processes are active, each may gain and lose control of the central processor many times before it can completely run a program. In disk operating systems like Unix, each process writes and reads data to and from its own "virtual" memory address space and the operating system actually stores the data for each process either in core memory at real addresses unrelated to the virtual addresses or on a disk. When an active process attempts to access a virtual address for a read or write operation, the operating system translates the virtual address to a real core memory address. If the data is on disk, the operating system must read it into core before the process can access it. Virtual addresses are mapped into real storage locations on a block-by-block basis with a block of contiguous virtual addresses corresponding to a block of contiguous real addresses. Data is also moved or "swapped" between core memory and disk files on a block-by-block basis and the virtual address space of the process is made up of a set of contiguous blocks of virtual addresses. Some of the associated blocks of real storage may reside in core and others may currently reside on disk, but in either place the blocks need not be contiguous nor stored in any particular order.
Since the virtual storage space of a process need not be mapped into a contiguous core area and may at any moment be mapped into secondary disk storage, real storage may be allocated among several processes in an efficient manner and the combined virtual address space of any one or several active processes may exceed the core address space of the system. In the prior art, block mapping has typically been accomplished using paging, segmentation and combination paging/segmentation methods. In a pure paging system, real and virtual storage blocks comprise pages of contiguous address locations of a fixed size with pages of virtual storage being mapped onto corresponding size pages of real storage. The use of fixed size pages minimizes the operating system overhead because it can maintain simple lists of available blocks of memory and disk addresses and need not compare the size of each block being swapped in or out of memory with the size of the available blocks for receiving it. The virtual address space of a process is mapped into the real storage space by a page list. The pure paging method is somewhat wasteful, however, in that not every page may be filled with data and therefore not every block of core memory or disk storage space will be fully utilized. This problems can be ameliorated if the pages are small, but making the pages too small requires the use of lengthy page lists which increases the load on core storage.
In a segmentation system, each block is a "segment" of continuous address space of variable size, sufficient to store a specified section of data associated with the process. The virtual address space of the process is mapped into the real storage space by a segment map table comprising a list of pointers to the real storage location of the first address of each segment. This method makes better use of each block of memory then the pure paging method but requires more operating system overhead to match segment sizes when transferring segments between core and disk storage.
In a combined segmentation/paging system, real storage is divided into equal sized pages while virtual storage is divided into variable sized segments. Each segment covers a virtual address space which can be mapped onto a whole number of real storage pages. The operating system locates a real address location corresponding to a virtual address by first utilizing a process map list to locate a segment page table and then using the page list to locate the real storage location of the page within the segment. Two independent processes can share the same segment if their process map lists point to the same page table which can save core or disk space when two processes are, for instance, running the same program text. This method has a disadvantage over pure paging and pure segmentation methods in requiring the operating system to perform two table lookups to translate a virtual address. However, a combined segmentation/paging method has an advantage over the other methods in that one process may copy large sections of data used by another process simply by establishing a process map list entry which points to an existing segment page table. The sharing of memory pages by more than one process is limited to cases where the data is "read only" in the sense that no process can change the data. Typically this may be the text portion rather than the data or stacked portions of a program. In the prior art, separate processes can share only entire segments; a process cannot map only into selected pages of a segment.
In systems such as Unix, a new process is initiated by a "fork" operation wherein a process is split into two independent concurrent processes called the "parent" and the "child" process. The parent and child do not share primary storage but do share pen disk files. Copies of all writable data segments must be made for the child at the time of the fork.
It would be advantageous to have a virtual memory system which employs both segmentation and paging but which requires only a single table lookup to translate virtual addresses into the storage locations. Such a system would also advantageously permit sharing of both read only and writable data segments by more than one process. This would eliminate the need for copying writable data segments for a child until such time as the child or the parent actually intends to access the data segments. The need for core space and therefore the need for disk operations to free core space would be reduced. Further savings in core and disk storage space could result if a process virtual space could map onto only a portion of a segment used by another.